Leetcode-Maximum Subarray

发表于 | 分类于 |

Maximum Subarray

最大子串和问题：从一个数组中找出一个子串使其和最大。
Description

tips:
子串是指数组中连续的若干个元素，而子序列只要求各元素的顺序与其在数组中一致，而没有连续的要求。

解题思路：
自己没有想出来，直接借鉴了网上的动态规划思路，我觉得下面是一些解决的关键点：

  • 对于array[1…n]，如果array[i…j]就是满足和最大的子串，那么对于任何k(i<=k<=j)，我们有array[i…k]的和大于0。具体证明
  • 假设已知0, .., k的最大和sum[k]以后，则0, …, k+1的最大和sum[k+1]分为以下两种情况：
    1）若sum[k]>=0，则sum[k+1]=sum[k]+A[k+1]。代码中即curSum = curSum+nums[i]。
    2）若sum[k]<0，另起一个SubArray，令sum[k+1]=A[k+1]。代码中即curSum = nums[i]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 0
    
    curSum = maxSum = nums[0]
    for i in range(1, len(nums)):
        curSum = max(nums[i], curSum+nums[i])
        maxSum = max(maxSum, curSum)
        
    return maxSum